\section{Proof of Theorem~\ref{thm:atleastktheorem}}
\label{sec:app main two}

%
%Let $t$, $V_i$ and $H^*$ be as in the theorem statement. Let $t'$ be the time that $V_i$ is last computed by Algorithm~\ref{algo:maintain}. Let $t''$ be the time Algorithm~\ref{algo:maintain} starts counting the number of edges in $V_i$.
%%
%%
%%We prove the theorem using the following lemmas.
%%
%The proof is similar to that of Theorem~\ref{theorem:approx densest} except that we use the following lemma instead of Lemma~\ref{lem: t prime prime to OPT}.

\begin{lemma}\label{lem:t prime prime to OPT for at least k}
$\rho_{t''}(V_i\cup \hat{V})>\frac{1-\delta}{3(1+\delta)}\min\left(\frac{\rho_{t'}(H^*)}{1+\delta}, \rho_{t'}(H^*)-3\delta \rho_t(H^*)\right)\,.$
\end{lemma}
\begin{proof}
Let $H'$ be the at-least-$k$ densest subgraph of $G_{t'}$. Note that
\begin{align}\label{eq:at least k one}
%\rho_{t''}(V_i)\geq \frac{1-\delta}{3(1+\delta)^2}\rho_{t'}(H')
\rho_{t'}(H^*)\leq \rho_{t'}(H')\,.
\end{align}

Now, define $\ell$, $H^1, \ldots, H^\ell$ and $D$ using Algorithm~\ref{algo:algo for proof} (which is similar to the process defined in \cite{KS} to prove that the algorithm in \cite{KS} is a 2-approximation). We note that we are not interested in the efficiency of this algorithm as it is only used to prove the approximation guarantee.
%
\begin{algorithm}
\caption{Defining $\ell$, $H^1, \ldots, H^\ell$ and $D$ for the proof of Lemma~\ref{lem:t prime prime to OPT for at least k}.} \label{algo:algo for proof}
\begin{algorithmic}[1]
\STATE Let $j=0$, $G_{t'}^0=G_{t'}$ and $D=\emptyset$. For any set of vertices $X$, let $E_{t'}(X)$ be the set of edges in the subgraph of $G_{t'}$ induced by $X$.
\WHILE{$|D|<k/(1-\delta)$ or $|E_{t'}(D)\cap E_{t'}(H')|< \frac{1}{3}E_{t'}(H')$}
\STATE For any $j$, let $H^j$ be the densest subgraph of $G_{t'}^j$.
\STATE $D=D\cup V(H^j)$.
\STATE Let $G_{t'}^{j+1}$ be the graph obtained from $G_{t'}^j$ by deleting nodes in $H^j$.
\STATE $j=j+1$.
\ENDWHILE
\STATE Let $\ell=j-1$.
\end{algorithmic}
\end{algorithm}

Note the following simple observation:
\begin{observation}\label{obs:48}\label{observation:proof of at least k}
For all $j=1, \ldots, \ell$, $\rho_{t'}(H^j)\geq \frac{2}{3}\rho_{t'}(H').$
\end{observation}
\begin{proof}
Since $|E_{t'}(D)\cap E_{t'}(H')|< \frac{1}{3}E_{t'}(H')$  in every iteration of the while loop,
$$|E_{t'}\left(V(G_{t'}^j)\cap V(H')\right)|\geq \frac{2}{3}|E_{t'}(H')|\,.$$
That is, there are at least $2/3$ fraction of edges of $H'$ left in $G_{t'}^j$. This implies that the density of subgraph of $G_{t'}^j$ induced by nodes in $H'$ is at least
%
\begin{eqnarray*}
 \rho_{t'}\left(V(G_{t'}^j)\cap V(H')\right) = \frac{|E_{t'}\left(V(G_{t'}^j)\cap V(H')\right)|}{|V(G_{t'}^j)\cap V(H')|} 
\geq  \frac{2}{3}\frac{|E_{t'}(H')|}{|V(H')|}  
= \frac{2}{3}\rho_{t'}(H')\,. 
\end{eqnarray*}
%
Since $H^j$ is the densest subgraph of $G_{t'}^j$,

$$
\rho_{t'}(H^j)\geq \rho_{t'}\left(V(G_{t'}^j)\cap V(H')\right)  \geq  \frac{2}{3}\rho_{t'}(H')$$
as claimed.
%$$
\end{proof}

%\begin{observation}
%$\rho_{t'}(D')\geq \frac{2}{3}\rho_{t'}(H').$
%\end{observation}
%\begin{proof}
%When the algorithm stops, either $|D|\geq k$ or $|E_{t'}(D)\cap E_{t'}(H')| \geq \frac{1}{3}|E_{t'}(H')|$. If $|D|\geq k$ then the above observation implies that
%$$\rho_{t'}(D')=\rho_{t'}(D)\geq \min_{1\leq j\leq \ell} \rho_{t'}(H_j)\geq \frac{2}{3}\rho_{t'}(H')\,.$$
%In the second case, we have
%$$\rho_{t'}(D')\geq \frac{1}{3} E_{t'}(H')/k \geq \frac{1}{3} E_{t'}(H')/|V(H')| \geq \frac{1}{3}\rho_{t'}(H')\,.$$
%\end{proof}

Let $i^*$ be the smallest index such that $V(D)\subseteq V_{i^*}$ and $V(D)\not\subseteq V_{i^*+1}$. Note that $i^*$ exists since the algorithm repeats until we get $V_j=\emptyset$. Now we consider two cases.
%: Either $|D|\geq k/(1-\delta)$ or $|E_{t'}(D)\cap E_{t'}(H')| \geq \frac{1}{3}|E_{t'}(H')|$ (these are two ways the while loop in Algorithm~\ref{algo:algo for proof} will stop).

%%%%%%%%%%%%%%%%%%%%%%%
% CASE 1
%%%%%%%%%%%%%%%%%%%%%%%

%{\bf Case 1: $|D|\geq k/(1-\delta)$.}

{\bf Case 1: $n_{i^*}\geq k$.} Let $v$ be any vertex in $V(D)\setminus V_{i^*+1}$. Let $j^*$ be such that $v\in V(H^{j^*})$. Note that Observation~\ref{observation:proof of at least k} implies that
\begin{align}\label{eq:at least k one one}
\rho_{t'}(H')\leq \frac{3}{2}\rho_{t'}(H^{j^*})\,.
\end{align}
%
Let $H_{t', i^*}$ be the subgraph of $G_{t'}$ induced by vertices in $V_{i^*}$. Note that
\begin{align}\label{eq:at least k one two}
\rho_{t'}(H^{j^*})\leq 2\deg_{H^{j^*}}(v) \leq 2\deg_{H_{t', i^*}}(v)\,.
\end{align}
%where $deg_{G_{t'}}(v)$ is the degree of $v$ in graph $G_{t'}$ and $E_{t'}(V_{i^*})$ is the number of edges in the subgraph of $G_{t'}$ induced by nodes in $V_{i^*}$.
%
The first inequality is because we can remove $v$ from $H^{j^*}$ and get a subgraph of $G_{t'}^{j^*}$ that has higher density than $H^{j^*}$ otherwise. The second inequality is because $H^{j^*}\subseteq H_{t', i^*}$ (since $V(H^{j^*})\subseteq D\subseteq V_{i^*}$).
%
%
%It follows from Observation~\ref{observation:proof of at least k} and the fact that $H^{j^*}\subseteq D\subseteq V_{i^*}$ that
%$$deg_{V_{i^*}}(v)\geq deg_{D}(v)\geq \frac{1}{3}\rho_{t'}(H')\,.$$
%
%
Since $v$ is removed from $V_{i^*}$,
\begin{align}\label{eq:at least k one three}
\deg_{H_{t',i^*}}(v)< (1+\delta) \frac{m_{i^*}}{n_{i^*}}
\end{align}
where $\delta=\epsilon/24$ as in Algorithm~\ref{algo:maintain}. By definition of $i$ and the fact that $n_{i^*}\geq k$,
\begin{align}\label{eq:at least k one four}
\frac{m_{i^*}}{n_{i^*}}=\frac{m_{i^*}}{\max(k, n_{i^*})}\leq \frac{m_i}{\max(k, n_i)}\,.
\end{align}
%
%It follows that
%$$3(1+\delta) \frac{m_i}{\max(k, n_i)} > 3deg_{V_{i^*}}(v)\geq \rho_{t'}(H')\,.$$
Note that $|V_i\cup \hat{V}|\leq n_i/(1-\delta)$ and $m_{i}\leq (1+\delta) |E_{t''}(V_{i})|$ with high probability\danupon{Need proof from previous section.}. It follows that
\begin{align}\label{eq:at least k one five}
\frac{m_i}{\max(k, n_i)}\leq \frac{1+\delta}{1-\delta}\rho_{t''}(V_{i}\cup \hat{V})\,.
\end{align}
%
Combining Eq.\eqref{eq:at least k one} with \eqref{eq:at least k one one}-\eqref{eq:at least k one five}, we get $\rho_{t'}(H^*)<3\frac{(1+\delta)^2}{1-\delta}\rho_{t''}(V_i\cup \hat{V})$\danupon{To polish: carefully take care of $\hat{V}$} and thus the lemma.


%%%%%%%%%%%%%%%%%%%%%%%%%%%
% CASE 2 %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%

%{\bf Case 2: $|D|<k/(1-\delta)$.} In this case $|E_{t'}(D)\cap E_{t'}(H')| \geq \frac{1}{3}|E_{t'}(H')|$ (by the stopping condition of Algorithm~\ref{algo:algo for proof}).

{\bf Case 2: $n_{i^*}<k$.} This implies that with high probability $|V_{i^*}|<(1+\delta)k$. Since $D\subseteq V_{i^*}$, $|D|<(1+\delta)k$. By the condition in the while loop of Algorithm~\ref{algo:algo for proof},
\begin{align}\label{eq:at least k two one}
|E_{t'}(V_{i^*})| \geq |E_{t'}(D)| \geq \frac{1}{3}|E_{t'}(H')|\,.
\end{align}
%
%{\bf Case 2: $|E_{t'}(D)\cap E_{t'}(H')| \geq \frac{1}{3}|E_{t'}(H')|$ } Since $V_{i^*}$ contains $D$, $|E_{t'}(V_{i^*})| \geq \frac{1}{3}|E_{t'}(H')|$. %
%
Note that $m_{i^*}\geq |E_{t'}(V_{i^*})|-Tr\geq \frac{1}{3}|E_{t'}(H')|-\delta k \rho_t(H^*)$.
%
%Moreover,
%$$\rho_{t}(H')=\frac{|E_{t}(H')|}{|V(H')|}\leq \frac{|E_{t'}(H')|+Tr}{|V(H')|}\leq  \frac{|E_{t'}(H')|+\delta k %\rho_t(H')}{|V(H')|}\leq (1+\delta)\rho_{t'}(H')$$
%\danupon{Not sure about the last inequality.}
Thus,
\begin{align}\label{eq:at least k two two}
\frac{m_{i^*}}{\max(k, n_{i^*})} &\geq \frac{\frac{1}{3}|E_{t'}(H')|-\delta k \rho_{t}(H^*)}{k} 
\geq \frac{1}{3}\rho_{t'}(H')-\delta \rho_t(H^*)\,.
\end{align}
By Eq.\eqref{eq:at least k one},
%\begin{align}\label{eq:at least k two three}
\begin{align}\label{eq:at least k two three}
\frac{m_{i}}{\max(k, n_{i})} &\geq \frac{m_{i^*}}{\max(k, n_{i^*})} 
\geq \frac{1}{3}\rho_{t'}(H')+\delta \rho_t(H^*) 
\geq \frac{1}{3}\rho_{t'}(H^*)-\delta \rho_t(H^*)\,.
\end{align}
%\end{align}
%
%Moreover,
%\begin{align}\label{eq:at least k two four}
%\rho_t(H^*)+Tr \geq \rho_{t'}(H^*)\,.
%\end{align}
%
Note that $|V_i\cup \hat{V}|\leq k/(1-\delta)$ and $m_{i}\leq (1+\delta) |E_{t''}(V_{i})|$ with high probability\danupon{Need proof from previous section.}. It follows that
%\begin{align}\label{eq:at least k two five}
\begin{eqnarray*}\label{eq:at least k two five}
\frac{m_i}{\max(k, n_i)} & \leq  \frac{(1+\delta)|E_{t''}(V_{i})|}{(1-\delta) k} \leq  \frac{1+\delta}{1-\delta}\rho_{t''}(V_{i}\cup \hat{V})\,.
\end{eqnarray*}
%\end{align}
%
Combining Eq.\eqref{eq:at least k one}, \eqref{eq:at least k two three} and \eqref{eq:at least k two five}, we get  $\rho_{t''}(V_i\cup \hat{V})>\frac{(1-\delta)(\rho_{t'}(H^*)-3\delta \rho_t(H^*))}{3(1+\delta)}$ and thus the lemma.
\end{proof}


\subsection{Proof of Observation~\ref{obs:48}}
\label{sec:app3}

\begin{proof}
Since $|E_{t'}(D)\cap E_{t'}(H')|< \frac{1}{3}E_{t'}(H')$  in every iteration of the while loop,
$$|E_{t'}\left(V(G_{t'}^j)\cap V(H')\right)|\geq \frac{2}{3}|E_{t'}(H')|\,.$$
That is, there are at least $2/3$ fraction of edges of $H'$ left in $G_{t'}^j$. This implies that the density of subgraph of $G_{t'}^j$ induced by nodes in $H'$ is at least
%$$
\begin{eqnarray*}
\rho_{t'}\left(V(G_{t'}^j)\cap V(H')\right) & = & \frac{|E_{t'}\left(V(G_{t'}^j)\cap V(H')\right)|}{|V(G_{t'}^j)\cap V(H')|}\\
 & \geq & \frac{2}{3}\frac{|E_{t'}(H')|}{|V(H')|}\\
&  = & \frac{2}{3}\rho_{t'}(H')\,.
\end{eqnarray*}
%$$
Since $H^j$ is the densest subgraph of $G_{t'}^j$,
$$\rho_{t'}(H^j)\geq \rho_{t'}\left(V(G_{t'}^j)\cap V(H')\right)\geq \frac{2}{3}\rho_{t'}(H')$$
as claimed.
\end{proof}

\begin{proof} [Proof of Theorem~\ref{thm:atleastktheorem}]
The theorem follows directly by using Lemma~\ref{lem:t prime prime to OPT for at least k} and translating the lower bound on $\rho_{t''}(V_i\cup \hat{V})$ to a lower bound on $\rho_{t}(V_i\cup \hat{V})$ (similar to the steps in proof of Theorem~\ref{theorem:approx densest}). As can be seen, the Lemma~\ref{lem:t prime prime to OPT for at least k} has a factor $\frac{1-\delta}{3(1+\delta)}$ as compared to a similar term of $\frac{(1-\delta)^2}{2(1+\delta)^2}$ in the case for densest subgraph. This is why we are only able to obtain a $(3+\epsilon)$-approximation to this theorem rather than a $(2+\epsilon)$-approximation previously. The proof for the theorem and the $(3+\epsilon)$-approximation is completed as before by translating $\rho_{t''}(V_i\cup \hat{V})$ to a lower bound on $\rho_{t}(V_i\cup \hat{V})$ and subsequently from the $\frac{1-\delta}{3(1+\delta)}$ term by plugging in the appropriate value for $\delta$ in terms of $\epsilon$.
\end{proof}
